package com.nowcoder.code.hjnc;

import com.algorithm.model.ListNode;

import java.util.Stack;

public class NC96 {

    public boolean isPail(ListNode head) {

        if (head == null) return false;
        if (head.next == null) return true;

        Stack<ListNode> stack = new Stack<>();

        ListNode slow = head;
        ListNode fast = head;
        stack.push(slow);
        while (fast != null && fast.next != null) {
            slow = slow.next;
            stack.push(slow);
            fast = fast.next.next;
        }

        if (fast == null) {
            stack.pop();
        }

        while (!stack.empty() && slow != null) {
            if (stack.pop().val != slow.val) {
                return false;
            }
            slow = slow.next;
        }

        return stack.empty() && slow == null;

    }

}
